import java.util.HashSet;
import java.util.Set;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-12-01
 * Time: 19:32
 */
//双向bfs
public class TurntableLock2 {
    public int openLock(String[] deadends, String target) {
        Set<String> deads = new HashSet<>();
        for(String s : deadends) deads.add(s);
        Set<String> q1 = new HashSet<>();
        Set<String> q2 = new HashSet<>();
        Set<String> visited = new HashSet<>();
        int step = 0;
        q1.add("0000"); //初始化起点和终点
        q2.add(target);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            Set<String> temp = new HashSet<>(); //用temp存储q1的扩散结果
            for (String cur : q1) { // 将q1中的所有节点向周围扩散
                if (deads.contains(cur)) continue;
                if (q2.contains(cur)) return step;
                visited.add(cur);
                for (int j=0;j<4;j++) { // 将一个节点未遍历的相邻节点加入集合
                    String up = plusOne(cur, j);
                    if (!visited.contains(up)) temp.add(up);
                    String down = minusOne(cur, j);
                    if (!visited.contains(down)) temp.add(down);
                }
            }
            step++; // 增加步数
            q1 = q2; // 此时 temp 相当于 q1，交换 q1 和q2，下一轮 while 会扩散 q2
            q2 = temp;
        }
        return -1;
    }
    public String plusOne(String cur, int j) {

        char[] ch = cur.toCharArray();
        if (ch[j] == '9') ch[j] = '0';
        else ch[j] += 1;
        return new String(ch);
    }
    public String minusOne(String cur, int j) {

        char[] ch = cur.toCharArray();
        if (ch[j] == '0') ch[j] = '9';
        else ch[j] -= 1;
        return new String(ch);
    }
}
